#pragma once
#include <iostream>
#include <vector>
#include <string>

namespace cr
{
    template <class T, class Container = std::vector<T>, class Comp = std::less<T>>
    class PriorityQueue
    {
        void adjust_down(int parent = 0)
        {
            // parent换位
            // int parent = 0;
            int child = parent * 2 + 1;
            int n = size();
            while (child < n)
            {
                // 先左孩子与右孩子作比较
                if (child + 1 < n && _comp(_cont[child], _cont[child + 1]))
                {
                    child++;
                }
                // 父子节点比较
                if (_comp(_cont[parent], _cont[child]))
                {
                    std::swap(_cont[parent], _cont[child]);
                    parent = child;
                    child = child * 2 + 1;
                }
                else
                    break;
            }
        }
        void adjust_up(int child = 0)
        {
            // child换位
            int n = size();
            child = n - 1;
            int parent = (child - 1) / 2;
            while (child > 0)
            {
                if (_comp(_cont[parent], _cont[child]))
                {
                    std::swap(_cont[parent], _cont[child]);
                    child = parent;
                    parent = (parent - 1) / 2;
                }
                else
                    break;
            }
        }

    public:
        // 默认构造
        PriorityQueue() {}

        // 拷贝构造
        PriorityQueue(const PriorityQueue &tmp)
        {
            Container cont(tmp._cont);
            std::swap(_cont, cont);
        }

        // 赋值
        const PriorityQueue &operator=(PriorityQueue tmp)
        {
            std::swap(_cont, tmp._cont);
            return *this;
        }

        // 迭代器构造
        template <class InputIterator>
        PriorityQueue(InputIterator first, InputIterator last,
                      const Comp &comp = Comp())
            : _comp(comp)// 因为lambda表达式没有默认的构造函数，所以通过对象传递
        {
            // 向下建堆法
            Container tmp(first, last);
            swap(_cont, tmp);

            int n = size() - 1;
            int parent = (n - 1) / 2;
            while (parent > 0)
            {
                adjust_down(parent);
                parent--;
                if (parent == 0)
                    adjust_down(parent);
            }
        }

        void push(const T &val)
        {
            _cont.push_back(val);
            adjust_up();
        }

        void pop()
        {
            assert(!empty());
            std::swap(_cont[0], _cont[size() - 1]);
            _cont.pop_back();
            adjust_down();
        }

        const T &top() const
        {
            assert(!empty());
            return _cont[0];
        }

        size_t size() const
        {
            return _cont.size();
        }
        bool empty() const
        {
            return _cont.empty();
        }

        void print()
        {
            for (auto &val : _cont)
            {
                std::cout << val << ' ';
            }
            std::cout << std::endl;
        }

    private:
        Container _cont;
        Comp _comp; // 仿函数对象
    };

    template <class T>
    std::ostream &operator<<(std::ostream &out, PriorityQueue<T> tmp)
    {
        while (!tmp.empty())
        {
            out << tmp.top() << ' ';
            tmp.pop();
        }
        return out;
    }
}